class Solution {
public:
    vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {
        vector<string> ret;
        vector<int> dp(words.size(),1);
        vector<int> pre(words.size(),-1);
        int maxId=0;
        for(int i=0;i<groups.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                if(groups[j]!=groups[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                    pre[i]=j;
                }
            }
            if( dp[i]>dp[maxId])
            {
                maxId=i;
            }
        }
        while(maxId!=-1)
        {
            ret.push_back(words[maxId]);
            maxId=pre[maxId];
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};
